/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.uniqueness;

import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Block;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.Region;

/**
 * Implementation of the Hidden Unique Rectangle solving technique.
 */
public class HiddenUniqueRectangleProducer implements IndirectHintProducer {

	@Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
		
		if (grid.hasExtraRegions()) return;

		// (1) find bivalue cells
        for (int y=0; y<9; y++) {
            for (int x=0; x<9; x++) {
                Cell cellA = grid.getCell(x, y);
                BitSet potentialsA = cellA.getPotentialValues();
                if (cellA.isEmpty() && potentialsA.cardinality()==2) {
                	findRectangle(grid, accu, cellA);
                }
            }
        }
    }
	
	/**
	 * Find Rectangle
	 * 
	 *   Cell A (ab)		Cell B (abx+)
	 *   Cell C (aby+)		Cell D (abz*)
	 */
	private void findRectangle(Grid grid, HintsAccumulator accu, Cell cellA) throws InterruptedException, StopHintProductionException {
        // (2) find opposite corner of Cell A -> Cell D:
        //	- must be within specific row or column range (to ensure that either cell B or C are in the same block as cell A)
        //	- must be in different block, row and column
        //	- must be empty
        //	- must have a+b as candidates
        
		// read cell A parameters
		int cellA_x = cellA.getX();
        int cellA_y = cellA.getY();
        BitSet cellAPotentials = cellA.getPotentialValues();
        int a = cellAPotentials.nextSetBit(0);
        int b = cellAPotentials.nextSetBit(a+1);
        Block cellABlock = (Block) grid.getRegionAt(Block.class, cellA);
        int cellABlockCode = cellABlock.getBlockCode();
        
        // compute min/max rows/columns
        int minCol = cellA_x/3*3;
        int maxCol = minCol+2;
        int minRow = cellA_y/3*3;
        int maxRow = minRow+2;
        
        for (int yPos=0; yPos<9; yPos++) {
            for (int xPos=0; xPos<9; xPos++) {
                if (Thread.interrupted()) throw new InterruptedException();
            	if ((yPos>=minRow && yPos<=maxRow) || (xPos>=minCol && xPos<=maxCol)) {
	                Cell cellD = grid.getCell(xPos, yPos);
	                BitSet cellDPotentials = cellD.getPotentialValues();
	                Block cellDBlock = (Block) grid.getRegionAt(Block.class, cellD);
	                int cellDBlockCode = cellDBlock.getBlockCode();
	                if (cellD.isEmpty() && cellDPotentials.get(a) && cellDPotentials.get(b) && 
	                	cellDBlockCode!=cellABlockCode && yPos!=cellA_y && xPos!=cellA_x) {
	                    // (3) retrieve other corners (Cell B and Cell C)
	                	Cell cellB = grid.getCell(xPos, cellA.getY());
	                	Cell cellC = grid.getCell(cellA.getX(), yPos);
	                	Block cellBBlock = (Block) grid.getRegionAt(Block.class, cellB);
	                    int cellBBlockCode = cellBBlock.getBlockCode();
	                	Block cellCBlock = (Block) grid.getRegionAt(Block.class, cellC);
	                    int cellCBlockCode = cellCBlock.getBlockCode();
	                	if ( (cellABlockCode==cellBBlockCode && cellCBlockCode==cellDBlockCode) ||
	                		 (cellABlockCode==cellCBlockCode && cellBBlockCode==cellDBlockCode)) {
		                	IndirectHint hint = isRectangleValid(cellA, cellB, cellC, cellD, a, b);
		                	if (hint!=null && hint.isWorth()) accu.add(hint);
	                	}
	                }
            	}
            }
        }
	}

	/**
	 * Checks whether the rectangle is a valid Hidden Unique Rectangle
	 * and creates an according hint (null if no valid rectangle was found).
	 * 
	 *   Cell A (ab)		Cell B (abx+)
	 *   Cell C (aby+)		Cell D (abz*)
	 */
	private IndirectHint isRectangleValid(Cell cellA, Cell cellB, Cell cellC, Cell cellD, int a, int b) {
        // (3) test for Hidden Unique Rectangle
        //	- cell B/C must be empty
        //	- cell B/C must contain candidates a and b plus at least one more candidate
        //	- cell D shares a house with cell B where only they have candidate a or b (either a or b) 
        //	- cell D shares a house with cell C where only they have candidate a or b (either a or b)

		if (cellB.isEmpty() && cellC.isEmpty()) {
			BitSet candidatesB = cellB.getPotentialValues();
			BitSet candidatesC = cellC.getPotentialValues();
			if (candidatesB.get(a) && candidatesB.get(b) && candidatesB.cardinality()>2 &&
				candidatesC.get(a) && candidatesC.get(b) && candidatesC.cardinality()>2) {
				// check if cell B and cell D share a house where only they have candidate a or b
				Region[] regionsBandD = findAlmostLockedSet(cellB, cellD, a, b);
				// check if cell C and cell D share a house where only they have candidate a or b
				Region[] regionsCandD = findAlmostLockedSet(cellC, cellD, a, b);
				
    			if (regionsBandD[0]!=null && regionsCandD[0]!=null) {
    				// Hidden Unique Rectangle found on value a
    		        List<Cell> rectangle = Arrays.asList(new Cell[] {cellA, cellB, cellC, cellD});
    	        	return new HiddenUniqueRectangleHint(rectangle, a, b, regionsBandD[0], regionsCandD[0]);
    			}
    			else if (regionsBandD[1]!=null && regionsCandD[1]!=null) {
    				// Hidden Unique Rectangle found on value b
    		        List<Cell> rectangle = Arrays.asList(new Cell[] {cellA, cellB, cellC, cellD});
    	        	return new HiddenUniqueRectangleHint(rectangle, b, a, regionsBandD[1], regionsCandD[1]);
    			}
			}
		}
		return null;
	}

	private Region[] findAlmostLockedSet(Cell cell1, Cell cell2, int value1, int value2) {
		Region[] result = new Region[2];
		for (Region region:cell1.getGrid().getRegionsAt(cell1)) {
			if (region.indexOf(cell2)>=0) {
				if (region.getNrOfPotentialPositions(value1)==2) {
					result[0] = region;
				}
				if (region.getNrOfPotentialPositions(value2)==2) {
					result[1] = region;
				}
			}
		}
		return result;
	}
	
	@Override
	public String getProducerName() {
		return HintResource.getString(R.string.producer_hidden_unique_rectangles);
	}
}